The present disclosure relates generally to location determination, and more particularly to generating and using a geocode trie to determine a location based on a geohash generated from location coordinates.
Traditional solutions for reverse geocoding have involved bounding box geometries with various packing optimizations. For example, a QuadTree structure can be used to represent non-overlapping geometries. In situations where overlapping geometries exist or which require minimum bound rectangles to be used, the QuadTree method returns multiple geometries in response to a single coordinate input. As a result, the system must solve what is commonly referred to as the “point-in-polygon” problem of matching to a single geometry. Various different solutions to this problem have been proposed (e.g., ray casting, matrix algebra), all leading to substantial inefficiency and resource requirements.
Complicating the matter, programming languages with garbage collection functionality (e.g., Java) are worse suited for resource intensive calculations. Specifically, the large number of dynamically allocated objects required in the computation can lead to long periods of garbage collection overhead and result in a system with high latency and low throughput characteristics.